import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-10-05
 * Time: 9:03
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Day10 {
    //617.合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null){
            return root2;
        }
        if (root2 == null){
            return root1;
        }
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right, root2.right);

        return root1;
    }

    //623.在二叉树中增加一行 - 标记
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 0 || depth == 1){
            TreeNode node = new TreeNode(val);
            if (depth == 1){
                node.left = root;
            }else{
                node.right = root;
            }
            return node;
        }
        if (root != null && depth > 1){
            root.left = addOneRow(root.left, val, depth > 2 ? depth - 1 : 1);
            root.right = addOneRow(root.right, val, depth > 2 ? depth - 1 : 0);
        }
        return root;
    }

    //647.二叉树的层平均值
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();
        if (root == null){
            return list;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (queue.size() != 0){
            int size = queue.size();
            double sum = 0;
            for (int i = 0; i < size; i++){
                TreeNode cur = queue.poll();
                sum += cur.val;
                if (cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null){
                    queue.offer(cur.right);
                }
            }
            list.add(sum / size);
        }
        return list;
    }

    //652.寻找重复子树 - 标记
    List<TreeNode> ans = new ArrayList<>();
    Map<String, Integer> map = new HashMap<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return ans;
    }

    String dfs(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        sb.append(root.val).append("*");
        String l = dfs(root.left);
        String r = dfs(root.right);
        sb.append(l).append("*").append(r);
        String res = sb.toString();
        if (!map.containsKey(res)) {
            map.put(res, 1);
        } else {
            if (map.get(res) == 1) ans.add(root);
            map.put(res, 2);
        }
        return res;
    }

    //653.两数之和IV - 输入二叉搜索树
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> hashset = new HashSet<Integer>();
        return preOrder(root,hashset,k);
    }
    public boolean preOrder(TreeNode root,HashSet<Integer> hashset,int k){
        if(root == null)
            return false;
        if(hashset.contains(k - root.val)){
            return true;
        }
        hashset.add(root.val);
        return preOrder(root.left,hashset,k) || preOrder(root.right,hashset,k);
    }

    //654.最大二叉树
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return maxTree(nums, 0, nums.length - 1);
    }

    public TreeNode maxTree(int[] nums, int begin, int end){
        if (begin > end){
            return null;
        }
        int max = findMax(nums, begin, end);
        TreeNode root = new TreeNode(nums[max]);
        root.left = maxTree(nums, begin, max - 1);
        root.right = maxTree(nums, max + 1, end);
        return root;
    }
    public int findMax(int[] nums, int begin, int end){
        int max = nums[begin];
        int maxIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (max < nums[i]){
                max = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}
